Hồi giáo truyền đến quần đảo Mã Lai thông qua những thương nhân Ả Rập và Ấn Độ trong thế kỷ 13, kết thúc thời kỳ của Ấn Độ giáo và Phật giáo.[11] Hồi giáo dần tiến đến khu vực, và trở thành tôn giáo của tầng lớp ưu tú trước khi truyền bá đến thường dân. Hồi giáo tại Malaysia chịu ảnh hưởng từ các tôn giáo trước đó và nguyên bản là không chính thống.[14]

Cảng Malacca trên bờ biển phía tây của bán đảo Mã Lai được thành lập vào năm 1402 theo lệnh của Parameswara, một hoàng tử của Srivijaya tẩu thoát khỏi Temasek (nay là Singapore)[14]. Sau khi tẩu thoát, Parameswara tiến về phía bắc để thành lập một khu định cư. Tại Muar, Parameswara cân nhắc đặt quốc gia mới của mình tại Biawak Busuk hoặc là Kota Buruk. Nhận thấy vị trí của Muar không phù hợp, ông tiếp tục đi về phía bắc. Ông tiến đến một làng cá tại cửa sông Bertam (tên cũ của sông Melaka), và thành lập khu định cư mà sau phát triển thành Vương quốc Malacca. Theo Biên niên sử Mã Lai, tại đây Parameswara trông thấy một con cheo cheo đá một con chó nghỉ bên dưới một cây Malacca, ông cho rằng đây là một điềm lành nên quyết định kiến lập một vương quốc mang tên Malacca. Ông cho xây dựng và cải tiến hạ tầng cho mậu dịch, Vương quốc Malacca thường được nhìn nhận là quốc gia độc lập đầu tiên tại bán đảo.[25]

Thời điểm Malacca hình thành, hoàng đế triều Minh phái các hạm đội đi khuếch trương mậu dịch. Đô đốc Trịnh Hòa ghé thăm Malacca và đưa Parameswara cùng mình trở tại Đại Minh, một sự công nhận vị thế quân chủ hợp pháp của ông. Đổi lại việc được triều cống thường lệ, hoàng đế Đại Minh cung cấp sự bảo hộ cho Malacca trước đe dọa liên tục về một cuộc tấn công của Xiêm. Người Hoa và người Ấn định cư tại bán đảo mã Lai trước và trong giai đoạn này là tổ tiên của cộng đồng Baba-Nyonya và Chetti hiện nay. Theo một giả thuyết, Parameswara trở thành một người Hồi giáo khi ông kết hôn với một công chúa của Pasai và lấy tước hiệu Ba Tư là "Shah", tự xưng là Iskandar Shah.[26] Biên niên sử Trung Hoa đề cập rằng vào năm Vĩnh Lạc thứ 9 (1414), con trai của quân chủ đầu tiên của Malacca đến chầu hoàng đế Đại Minh để thông báo rằng cha mình đã từ trần. Con trai của Parameswara sau đó được hoàng đế Đại Minh chính thức công nhận là quân chủ thứ nhì của Malacca, mang tước Raja Sri Rama Vikrama, và được các thần dân Hồi giáo biết đến với tước Sultan Sri Iskandar Zulkarnain Shah hay Sultan Megat Iskandar Shah. Ông cai trị Malacca từ năm 1414 đến năm 1424.[26][27] Thông qua ảnh hưởng của những người Hồi giáo Ấn Độ, và ở một mức độ thấp hơn là người Hồi từ Trung Quốc, Hồi giáo trở nên ngày càng phổ biến trong thế kỷ 15.

Sau một giai đoạn ban đầu triều cống cho Ayutthaya,[14] Malacca nhanh chóng đàm nhận vị trí trước đây của Srivijaya, thiết lập quan hệ độc lập với Đại Minh, và khai thác vị trí chi phối eo biển Malacca để kiểm soát mậu dịch hàng hải Trung-Ấn, vốn trở nên ngày càng quan trọng khi các cuộc chinh phục của người Mông Cổ cắt đứt tuyến đường bộ giữa Trung Hoa và phương Tây.

Trong vòng vài năm sau khi thành lập, Malacca chính thức chấp nhận Hồi giáo. Parameswara trở thành một người Hồi giáo, và do vậy việc cải biến tôn giáo của người Mã Lai sang Hồi giáo được tăng tốc trong thế kỷ 15.[20] Quyền lực chính trị của Malacca giúp truyền bá nhanh chóng Hồi giáo trên khắp quần đảo. Malacca là một trung tâm thương nghiệp quan trọng vào đương thời, thu hút mậu dịch từ khắp khu vực.[20] Đến đầu thế kỷ 16, cùng với Malacca trên bản đảo Mã Lai và nhiều bộ phận của Sumatra, vương quốc Demak tại Java, và các vương quốc khác trên khắp quần đảo Mã Lai ngày càng cải sang Hồi giáo,[28] nó trở thành tôn giáo chi phối đối với người Mã Lai, và tiến xa đến Philippines ngày nay.

Vương triều Malacca tồn tại trong hơn một thế kỷ, song trong thời gian này nó trở thành trung tâm của văn hóa Mã Lai. Hầu hết các quốc gia Mã Lai trong tương lai đều bắt nguồn trong giai đoạn này.[11] Malacca trở thành một trung tâm văn hóa, tạo ra mô hình của văn hóa Mã Lai hiện đại: một sự pha trộn của các yếu tố Mã Lai bản địa và các yếu tố Ấn Độ, Trung Hoa và Hồi giáo. Những phong cách của Malacca trong văn chương, nghệ thuật, âm nhạc, vũ đạo và trang phục, và các tước hiệu trong triều đình, được nhận định là tiêu chuẩn đối với mọi người Mã Lai. Triều đình Malacca cũng đem lại thanh thế lớn cho tiếng Mã Lai, thứ tiếng nguyên tiến hóa tại Sumatra và được đưa đến Malacca khi nó hình thành. Tiếng Mã Lai trở thành ngôn ngữ chính thức của toàn bộ các bang tại Malaysia, song các ngôn ngữ địa phương vẫn tồn tại ở một số nơi. Sau khi Malacca sụp đổ, Vương quốc Brunei trở thành trung tâm lớn của Hồi giáo trong khu vực.[11]